package main

import "fmt"

func main() {
	nums := []int{100, 4, 200, 1, 3, 2}
	fmt.Printf("longestConsecutive(nums): %d\n", longestConsecutive(nums))
}

/**
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。//-
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。//-
*/ //-
//-
/**
思考： 连续的序列是 x, x+1, x+2, x+3,...//-
1、如果我们随机找到了一个数 x， 存在x+1，那么我们就继续从x+1，开始找x+2，找到多少算多少，记录最长的那个//-
2、那么下次随机 也可能随机到了 x+3， 我们按照步骤1再来做一次的话就重复了//-
3、所以我们只需要随机找一个数y，存在 y-1，就从y-1开始继续找，记录最长的那个//-
4、那么下次随机，也可能随机到了y+3，按照步骤3，会找到y，发现如果从y+3开始的序列并不是最大值，而是y//-
5、所以只需要考虑从y-1开始//-
*/
func longestConsecutive(nums []int) int {
	m := make(map[int]bool, len(nums))
	for _, num := range nums {
		m[num] = true
	}

	maxLen := 0
	for num := range m {
		if m[num-1] {
			continue
		}
		currentNum := num
		currentLen := 1
		for m[currentNum+1] {
			currentNum++
			currentLen++
		}
		if currentLen > maxLen {
			maxLen = currentLen
		}
	}
	return maxLen
}
